import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=1013 lang=java
 *
 * [1013] 将数组分成和相等的三个部分
 *
 * https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/description/
 *
 * algorithms
 * Easy (52.60%)
 * Likes:    15
 * Dislikes: 0
 * Total Accepted:    5.6K
 * Total Submissions: 10.6K
 * Testcase Example:  '[0,2,1,-6,6,-7,9,1,2,0,1]'
 *
 * 给定一个整数数组 A，只有我们可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
 *
 * 形式上，如果我们可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] +
 * ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
 *
 *
 *
 * 示例 1：
 *
 * 输出：[0,2,1,-6,6,-7,9,1,2,0,1]
 * 输出：true
 * 解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
 *
 *
 * 示例 2：
 *
 * 输入：[0,2,1,-6,6,7,9,-1,2,0,1]
 * 输出：false
 *
 *
 * 示例 3：
 *
 * 输入：[3,3,6,5,-2,2,5,1,-9,4]
 * 输出：true
 * 解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
 *
 *
 *
 *
 * 提示：
 *
 *
 * 3 <= A.length <= 50000
 * -10000 <= A[i] <= 10000
 *
 *
 */

// @lc code=start
class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int[] dp = new int[A.length];
        int sum = 0;
        for(int i=0; i < A.length; i++) {
            sum += A[i];
            dp[i] = sum;
        }
        if(sum % 3 != 0) {
            return false;
        }
        for(int i=0; i < A.length-2;i++) {
            if(dp[i] * 3 == sum) {
                //System.out.println(sum+" "+ dp[i]);
                for(int j=i+1; j < A.length-1; j++) {
                    if(dp[j] == dp[i] << 1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
// @lc code=end

class Solution {
    public boolean canThreePartsEqualSum (int[] A) {
        int sum =
    }
}



